COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00008 ENDMK
C⊗;
\input macro[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\noindent A03[AOO,rwf]
\bigskip
The following several pages by Jonathan Goldstine reflect an independent view
of computability very similar to mine.  If you like, skip all but the few
underlined bits.
\vfill\eject
Some years ago I quit trying to teach the elements of computer programming
to the average student.  I program deductively, not inductively, and my
track record of economically important algorithms shows the value of the
method, but I don't know how, in one academic quarter, to convince the
typical student to adopt my intellectual style.  So now I teach an honors
section of the first course in programming, with advance warning of a high
level of abstraction, and with a calculus prerequisite.  Here are a few
samples.

{$\bullet$} In a graphics hidden-line application, we want to know whether two 
line segments ${\rm AB}$ and ${\rm CD}$ intersect.  First we break this 
down into two 
subproblems: are the points ${\rm A}$ and ${\rm B}$ on opposite sides of 
the line ${\rm L}$
through ${\rm C}$ and ${\rm D}$, and symmetrically.  But ${\rm A}$ and ${\rm B}$ 
are on the same side
of ${\rm L}$ if the oriented triangles ${\rm ACD}$ and ${\rm BCD}$ have the 
same orientation.
The students already have seen a formula for area, that takes a positive sign
for clockwise orientation, so if ${\rm Area(ACD)} \times {\rm Area(BCD)}$
 and ${\rm Area(CAB)} \times {\rm Area(DAB)}$ are both negative, the 
segments intersect; ${\rm Area(ACD)} = (a↓xc↓y - c↓xa↓y) + (c↓xd↓y - 
d↓xc↓y) +
(d↓xa↓y + a↓xd↓y)$.  I am not saying this is something a good computer
programmer has to know.  I am saying this is how a good designer of algorithms
has to think.

{$\bullet$} In a spelling-correction application, I have two strings $x$ 
and $y$, and I want to find the smallest number of editing operations that will
change $x$ to $y$.  So I look at the first letters of $x$ and $y$.  If
$x = Au$ and $y = Av$, I consider the reduced problem of changing $u$ to $v$.
If $x = Au$ and $y = Bv$, I consider several cases, such as changing
$u$ to $Bv$, preceded by dropping an $A$ from $Au$, or changing $u$ to $v$,
preceded by substituting $B$ for $A$ (there are a few other cases).  All
the subproblems that arise involving changing some suffix of $x$ to a suffix of
$y$, so by iteration I tabulate the answers of all the suffix-to-suffix
subproblems, starting with the smallest.  This paradigm is called dynamic
programming.  The higher-level paradigm is to look for such paradigms
that reduce the size of a problem.

I have, mainly in computer-typeset camera-ready form, about three or four
hundred pages of a textbook on algorithms and programming.  When I finish the
computability book, I will turn fully to the programming book.

This is not just another attempt to teach software engineering at the 
introductory level.  Software engineering is the management of complexity in
large algorithms.  You can't have a software engineering problem until you
can invent a large algorithm that is good enough to be worth implementing well.
\vfill\eject
Also from Minsky:  ``Instead of helping students find new paradigms, we
vaccinate with structured programming against the dread disease of novelty.''
Structured programming?  We must have something to write about before we start
worrying about rhetoric!
\bye